#include <iostream>
#include <set>
#include <unordered_set>
#include <vector>
#include <cstdlib>
#include <ctime>
using namespace std;

void test2()
{
	const int N = 1000000;
	srand((unsigned int)time(0));

	set<int> s;
	unordered_set<int> us;

	vector<int> v;
	v.reserve(N);
	for (int i = 0; i < N; i++)
	{
		v.push_back(rand() + i);
	}

	int begin1 = clock();
	for (auto& e : v)
	{
		s.insert(e);
	}
	int end1 = clock();

	int begin2 = clock();
	for (auto& e : v)
	{
		us.insert(e);
	}
	int end2 = clock();

	cout << "set insert: " << end1 - begin1 << endl;
	cout << "unordered_set insert: " << end2 - begin2 << endl;

	int begin3 = clock();
	int m1 = 0;
	for (auto& e : v)
	{
		auto ret = s.find(e);
		if (ret != s.end())
		{
			++m1;
		}
	}
	int end3 = clock();

	int begin4 = clock();
	int m2 = 0;
	for (auto& e : v)
	{
		auto ret = us.find(e);
		if (ret != us.end())
		{
			++m2;
		}
	}
	int end4 = clock();

	cout << "set find: " << end3 - begin3 << "->" << m1 << endl;
	cout << "unordered_set find: " << end4 - begin4 << "->" << m2 << endl;

	int begin5 = clock();
	for (auto& e : v)
	{
		s.erase(e);
	}
	int end5 = clock();

	int begin6 = clock();
	for (auto& e : v)
	{
		us.erase(e);
	}
	int end6 = clock();

	cout << "set erase: " << end5 - begin5 << endl;
	cout << "unordered_set erase: " << end6 - begin6 << endl;
}

void test1()
{
	set<int> s = { 5,2,3,7,1,8,9,6 };
	for (auto& e : s)
	{
		cout << e << " ";
	}
	cout << endl;

	unordered_set<int> us = { 5,2,3,7,1,8,9,6 };
	for (auto& e : us)
	{
		cout << e << " ";
	}
	cout << endl;
}

int main()
{
	//test1();
	test2();

	return 0;
}